# Copyright (c) 2012 by Adam Wolenc <adamdblu@gmail.com>.
# All rights reserved.

# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:

#     * Redistributions of source code must retain the above copyright notice,
#       this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above copyright
#       notice, this list of conditions and the following disclaimer in the
#       documentation and/or other materials provided with the distribution.
#     * The name(s) of the copyright holder(s) may not be used to endorse or
#       promote products derived from this software without specific prior
#       written permission.

# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) "AS IS" AND ANY EXPRESS
# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
# EVENT SHALL THE COPYRIGHT HOLDER(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

import copy
import string
import re
import sys

edgelen = 4

# Set up the board. Use single letters or QU for Qu.
grid = (('S', 'E', 'O', 'N'),
        ('H', 'T', 'R', 'E'),
        ('T', 'U', 'E', 'S'),
        ('QU', 'P', 'F', 'L'))
assert(len(grid) == edgelen)
# Set up double and triple letters.
lmult = ((1,1,1,3),
         (1,3,1,1),
         (1,1,1,1),
         (3,1,1,1))
# Set up double and triple word bonuses.
wmult = ((1,1,1,1),
         (1,1,1,1),
         (1,3,1,1),
         (1,1,1,1))
# Set up points associated with each letter.
#         A B C D E F G H I J  K L M N O P Q  R S T U V W X Y Z
points = [1,4,4,2,1,4,3,3,1,10,5,2,4,2,1,4,10,1,1,1,2,5,4,8,3,10]
# Set up word length bonus.
word_length_bonus = [0,0,0,0,0,3,6,10,15,20,20,20,20,20,20,20,20,20]


class Result(object):
  def __init__(self, score, path):
    self.score = score
    self.path = path

def load_dictionary(fn):
  # Load a word list from the supplied file name.
  d = open(fn, 'r')
  for word in d:
    if word.lower() == word:
      # Ignore case and punctuation.
      # Only include the word if it can be composed of letters in the grid.
      stripped_word = word.upper().strip(string.whitespace + string.punctuation)
      if word_filter_re.match(stripped_word):
        words.add(stripped_word)
  d.close()

def choices(used, pos=None):
  # Given a boolean matrix indicating what letters have been used so far in a
  # partial solution, and cannot be used again, return a list of letter
  # positions that are possible for the next move.
  ret = []
  if not pos:
    # Opening move. All moves are possible.
    for i in range(edgelen):
      for j in range(edgelen):
        ret.append((i,j))
  else:
    # Continued move.
    for i in range(pos[0] - 1, pos[0] + 2):
      for j in range(pos[1] - 1, pos[1] + 2):
        if ((i,j) == pos or  i < 0 or j < 0 or i >= edgelen or j >= edgelen):
          continue
        if used[i][j]:
          continue
        ret.append((i,j))
  return ret

def score(used):
  # Given a boolean matrix indicating what letters have been used in a valid
  # solution, return the solution's score.
  this_wmult = 1
  sc = 0
  used_count = 0
  for i in range(edgelen):
    for j in range(edgelen):
      if used[i][j]:
        used_count += 1
        if wmult[i][j] > this_wmult:
          this_wmult = wmult[i][j]
        if grid[i][j] == 'QU':
          code = ord('Q')
        else:
          code = ord(grid[i][j])
        sc += points[code - ord('A')] * lmult[i][j]
  # Special case for 2-letter words. Letter scores and multipliers don't matter
  # and are forced to a total of 1 point, but word multipliers still apply.
  if used_count == 2:
    sc = 1
  return sc * this_wmult + word_length_bonus[used_count]

def seek(sofar=None, used=None, pos=None):
  # Firstly, if sofar is a word, add it to the solution list. Compose a pretty
  # line indicating which tiles were used to form this word.
  # Secondly, recursively explore if sofar contains the beginning of any other
  # solutions (and add those to the solution list as well.)
  if used is None:
    # This matrix contains a boolean value for each letter position indicating
    # whether a letter has been used in the solution under consideration.
    # At first, no letter has been used.
    used = [[False]*edgelen for _ in range(edgelen)]
    assert sofar is None
    sofar = ''

  if len(sofar) >= 2 and sofar in words:
    sc = score(used)
    if ((sofar in results.keys() and sc > results[sofar].score) or
        sofar not in results.keys()):
      path = ''
      for rownum, row in enumerate(used):
        path += '|'
        for colnum, col in enumerate(row):
          path += grid[rownum][colnum] if used[rownum][colnum] else '.'
      res = Result(sc, path)
      results[sofar] = res

  if any([word.startswith(sofar) for word in words]):
    for choice in choices(used, pos):
      i, j = choice
      used1 = copy.deepcopy(used)
      used1[i][j] = True
      seek(sofar + grid[i][j], used1, choice)

words=set()
word_filter_re = re.compile(
    '^[' + ''.join([''.join(r) for r in grid]) + ']{2,' + str(edgelen**2)+'}$')
load_dictionary('/usr/share/dict/words')
load_dictionary('supp.txt')
sys.stderr.write('Focusing on ' + str(len(words)) + ' word dictionary.\n')


results = dict()
seek()
for word, result in results.iteritems():
  print '\t'.join([word.ljust(edgelen**2, ' '), str(result.score), result.path])

